/**
 * create by Sun
 * 2018/8/31
 */
public class huiwenzufuchuan {

    static String huiwen(String s){
        boolean[][] dp=new boolean[1000][1000];
        int i,j;
        int max=0;
        int begin=0;
        for(i=0;i<s.length();i++){
            for(j=0;j<=i;j++){
                //j---i的距离
                if(i-j<2){
                    if(s.charAt(i)==s.charAt(j)){
                        dp[j][i]=true;
                    }else{
                        dp[j][i]=false;
                    }
                }else{
                    dp[j][i]=(s.charAt(j)==s.charAt(i)&&dp[j+1][i-1]);
                }
                if(i-j+1>max&&dp[j][i]){
                    max=i-j+1;
                    begin=j;
                }
            }
        }
        return s.substring(begin,begin+max);
    }
    public static void main(String[] args) {
        String s="babab";
        huiwen(s);
    }


}
